To form signatures for test purposes, linear signatures are formed for detecting errors, among other things, in order to detect one or more function errors. While linear signature formation is common and also entirely sufficient for error detection of this type, nonlinear signatures, such as the so-called hash functions, are advantageous for cryptographic methods. In nonlinear signatures, use is made of the fact that it is very difficult to calculate the original data on the basis of the signature, or the fact that it is very difficult to manipulate the data in such a way that the same signature may be generated from the original data and the manipulated data if one starts in the same initial state or a known deviation from the initial state.
It is therefore advantageous to generate the signature in a nonlinear manner or to introduce a nonlinearity into the circuit. Shift registers of the standard type and the modular type and methods of this type are known. The operator usually performs an antivalent logic operation, which results in linear feedback. Using an (aforementioned) hash function instead of the shift register makes it possible to achieve nonlinearity. However, hash functions are extremely complex to implement, necessitating an extensive calculation and a large memory.
Alternatively, one could provide a nonlinear operator instead of a linear operator in the signal feedback, the nonlinear operator performing, for example, a NAND, NOR, AND, OR function or another nonlinear function. Although this makes the signature formation as a whole nonlinear, the advantageous characteristic of a linear feedback shift register having a primitive polynomial is lost. The advantageous characteristic of the linear feedback shift register is that all assignments except for “000 . . . 0” are achieved. The use of a nonlinear operator could thus enable fewer states to be achieved and increase the probability of different data being mapped to the same signature.